Boolean Algebra and Theorems

Part 1: What is Boolean Algebra

Boolean Algebra is a mathematical system used to represent and manipulate logical expressions. It is a set of elements (usually 0 and 1, representing false and true) with operations (AND, OR, NOT) that follow specific rules.

Part 2: Basic operations: AND, OR, NOT

Boolean algebra and logic gates are closely intertwined because they both deal with binary values (0 and 1) and logical operations. In essence, logic gates are the physical implementation of Boolean algebra operations.

Part 2.1 AND Laws

A * 1 = A	A * A’ = 0
A * 0 = 0	A * A = A

Part 2.2 OR Laws

A + 1 = 1	A + A’ = 1
A + 0 = A	A + A = A

Part 2.3 Complementation Laws

A’’ = A

1’ = 0

0’ = 1

Part 3: Laws in Boolean Algebra

Part 3.1 Associative law

x + (y + z) = (x + y) + z = x + y +z

x(yz) = (xy)z +xyz

Part 3.2 Commutative law

xy = yz

x + y = y + x

Part 3.3 Distributive Law

x(y + z) = xy + xz

(w + x)(y + z) = wy + xy + wz + xz

x + xy = x

x + x’y = x + y

Part 4: Other Postulates and Theorems of Boolean Algebra

Part 4.1 De Morgan’s Theorem

De Morgan's Laws are two theorems in Boolean algebra that express the negation of a disjunction (OR) or a conjunction (AND) in terms of the conjunction or disjunction of the negations of the original operands.

I.	(A + B + C…)’ = A’ + B’ + C’ + ...
II.	(A * B * C…)’ = A’ + B’ + C’ …

Part 4.2 Absorption Law

A + (A * B) =A

A(A + B) =A

Part 4.2 Consensus Laws

A * B + A' * C + B * C = A * B + A' * C

(A + B) * (A' + C) * (B + C) = (A + B) * (A' + C)

Example No. 1

Simplify the Boolean Expression: BD + (DD + B’) B

Solution:

Apply the AND Law: (AA=A)

= BD + (DD + B’) B

= BD + (D + B’) B

Apply Distribution law

= BD + (D + B’) B

= BD + (BD + BB’)

Apply AND Law (AA’ = 0)

= BD + (BD + BB’)

= BD + (BD + 0)

Apply OR Law: A + 0 = A

= BD + (BD + 0)

= BD + (BD)

Apply OR Law: A + A = A

=BD + BD

=BD

Therefore, our answer is: BD + (DD + B’) B = BD

Example No. 2

Simplify the Boolean Expression: D((DC)’ + (A’D)’) + (AD’)’

Solution:

Apply the De Morgan Theorem: (A + B + C…)’ = A’ + B’ + C’ + ...

= D((DC)’ + (A’D)’) + (AD’)’

= D((DC)’ + (A’D)’) + A’ + D’’

Apply the Complementation Laws: A” = A

 = D((DC)’ + (A’D)’) + A’ + D’’

= D((DC)’ + (A’D)’) + A’ + D

Apply the De Morgan Theorem: (A * B * C…)’ = A’ + B’ + C’ …

= D ((DC)’ + (A’D)’) + A’ + D

= D (D’ + C’ + (A’D)’) + A’ + D

Apply the De Morgan Theorem: (A * B * C…)’ = A’ + B’ + C’ …

= D (D’ + C’ + (A’D)’) + A’ + D

= D (D’ + C’ + A’’+D’) + A’ + D

Apply the Complementation Laws: A” = A

= D (D’ + C’ + A’’ + D’) + A’ + D

= D (D’ + C’ + A + D’) + A’ + D

Apply OR Laws: A + A = A

= D (D’ + C’ + A + D’) + A’ + D

= D (D’ + C’ + A) + A’ + D

Apply Distributive Law: x + xy = x

= D (D’ + C’ + A) + A’ + D

= D + A’

Therefore, our answer is: = D + A’

Example No. 2

Simplify the Boolean Expression: BA + D(AD+(BC)’)

Solution:

Apply the De Morgan Theorem: (A * B * C…)’ = A’ + B’ + C’ …

= BA + D (AD+ (BC)’)

= BA + D (AD+ B’ + C’)

Apply Distributive Law: x(y + z) = xy + xz

= BA + D (AD+ B’ + C’)

= BA + (DAD+ DB’ + DC’)

Apply AND Law: AA=A

= BA + (DAD+ DB’ + DC’)

= BA + DA+ DB’ + DC’

Apply Consensus Law: A * B + A' * C + B * C = A * B + A' * C

= BA + DA+ DB’ + DC’

= BA + DB’ + DC’

Therefore, our answer is: = BA + DB’ + DC’